import java.io.Serializable;
import java.util.*;

public class Sand_table implements Serializable {
    int[][] table;
    int height;
    int width;
    int bln=0;
    Deque<Body_joint> snake;
    Deque<Body_joint> map;
    int dx, dy;
    Body_joint food;
    boolean isAI;
    int speed;
    public Sand_table(int height, int width) {
        this.height = height;
        this.width = width;
        table = new int[height][width];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                table[i][j] = 0;
            }
        }
        snake = new ArrayDeque<Body_joint>();
        for (int i = 1; i <= 5; i++) {
            addBody(height / 2 - i, width / 2);
        }
        addBody(height / 2 - 5, width / 2 - 1);
        addBody(height / 2 - 5, width / 2 - 2);
        for (int i = 1; i <= 3; i++) {
            addBody(height / 2 - 5 + i, width / 2 - 2);
        }

        food = new Body_joint(height / 2 - 4, width / 2 - 1);
        table[height / 2 - 4][width / 2 - 1] = 2;
        dx = 1;
        dy = 0;
        //NewFood();
        isAI = true;
        speed=500;
        btable = new int[height][width];
    }

    public void addBody(int x, int y) {
        snake.addFirst(new Body_joint(x, y));
        table[x][y] = 1;
    }
    public void addSpeed()
    {
        if(speed>200)speed-=5;
        else speed-=1;
        if(speed<5)speed=5;
    }
    public void decSpeed()
    {
        if(speed<200)speed+=1;
        else speed+=5;
        if(speed>500)speed=500;
    }
    public void NewFood() {
        int ftemp = RandomNumber(1, height * width - snake.size()-bln);
        addSpeed();
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (table[i][j] == 0) ftemp--;
                if (ftemp == 0) {
                    food.setX(i);
                    food.setY(j);
                    table[i][j] = 2;
                    return;
                }
            }
        }
    }

    public int RandomNumber(int min, int max) {
        return new Random().nextInt(max) % (max - min + 1) + min;
    }

    public boolean Move() {
        if (isAI) {
            if (mnsnake == null || mnsnake.isEmpty()) AImove();

            if (snake.getFirst().equals(mnsnake.getFirst())) {
                dx = mnsnake.getFirst().getDx();
                dy = mnsnake.getFirst().getDy();
                // System.out.println(dx+" "+dy);
                mnsnake.pollFirst();
            }

        } else {
            if (mnsnake != null && !mnsnake.isEmpty()) mnsnake.clear();
        }
        // System.out.println(dx+" "+dy);
        Body_joint btemp = snake.getFirst();
        int btx = btemp.getX() + dx;
        int bty = btemp.getY() + dy;
        if (btx >= 0 && btx < height && bty >= 0 && bty < width) {
            snake.addFirst(new Body_joint(btx, bty));
            btemp = snake.pollLast();
            table[btemp.getX()][btemp.getY()] = 0;
            if (table[btx][bty] == 1 || table[btx][bty] == 3) return false;
            if (table[btx][bty] == 2) {
                snake.addLast(btemp);
                table[btemp.getX()][btemp.getY()] = 1;
                if(snake.size()>=width*height)return false;
                NewFood();
            }
            table[btx][bty] = 1;
            return true;
        }
        return false;
    }


    int[][] btable;
    ;
    Deque<Body_joint> mnsnake;

    public void AImove() {
        if (mnsnake == null) mnsnake = new ArrayDeque<>();
        else mnsnake.clear();

        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                btable[i][j] = -table[i][j];
                if(btable[i][j]==-3)btable[i][j]=-1;
            }
        }

        if (canGet(snake.getFirst(), food, btable, mnsnake) > 0) {
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    btable[i][j] = -table[i][j];
                }
            }
            for (Body_joint body_joint : mnsnake) {
                btable[body_joint.getX()][body_joint.getY()] = -1;
            }
            if (canGet(food, snake.getLast(), btable, null) > 0) {
                return;
            }



        }
        mnsnake.clear();
        int maxx = 0;
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i == j || i * j != 0 || isOut(snake.getFirst().getX() + i, snake.getFirst().getY() + j))
                    continue;
                if (table[snake.getFirst().getX() + i][snake.getFirst().getY() + j] != 0) continue;
                for (int ii = 0; ii < height; ii++) {
                    for (int jj = 0; jj < width; jj++) {
                        btable[ii][jj] = -table[ii][jj];
                    }
                }
                btable[snake.getLast().getX()][snake.getLast().getY()] = 0;
                int t = canGet(new Body_joint(snake.getFirst().getX() + i, snake.getFirst().getY() + j), snake.getLast(), btable, null);
                t+=snake.getFirst().getDis(food);
                if (maxx < t) {
                    maxx = t;
                    if (mnsnake.isEmpty())
                        mnsnake.addFirst(new Body_joint(snake.getFirst().getX(), snake.getFirst().getY()));
                    mnsnake.getFirst().setDx(i);
                    mnsnake.getFirst().setDy(j);
                }
            }
        }
        if(mnsnake.isEmpty())
        {
            mnsnake.addFirst(new Body_joint(snake.getFirst()));
            mnsnake.getFirst().setDx(snake.getLast().getX()-snake.getFirst().getX());
            mnsnake.getFirst().setDy(snake.getLast().getY()-snake.getFirst().getY());
        }
    }

    public int canGet(Body_joint qd, Body_joint zd, int[][] map, Deque<Body_joint> road) {


        map[qd.getX()][qd.getY()] = map[zd.getX()][zd.getY()] = 0;
        PriorityQueue<Body_joint> bfslist = new PriorityQueue<>();
        int[][] ddx = new int[height][width];
        int[][] ddy = new int[height][width];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                ddx[i][j] = ddy[i][j] =  0;
            }
        }
        qd.setS(1 + qd.getDis(zd));
        bfslist.add(qd);
        map[qd.getX()][qd.getY()] = 1;
        Body_joint btemp, bbtemp = null;
        while (!bfslist.isEmpty()) {
            if (map[zd.getX()][zd.getY()] != 0) break;
            btemp = bfslist.poll();
            if(map[btemp.getX()][btemp.getY()]<btemp.getS()-btemp.getDis(zd)&&map[btemp.getX()][btemp.getY()]!=0) continue;

            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    if (i == j || i * j != 0 || isOut(btemp.getX() + i, btemp.getY() + j) ||  map[btemp.getX() + i][btemp.getY() + j] == -1)
                    continue;//不可抵达或close
                    if (map[btemp.getX() + i][btemp.getY() + j] == 0||map[btemp.getX() + i][btemp.getY() + j] > map[btemp.getX()][btemp.getY()] + 1) {
                        map[btemp.getX() + i][btemp.getY() + j] = map[btemp.getX()][btemp.getY()] + 1;
                        bbtemp = new Body_joint(btemp.getX() + i, btemp.getY() + j, i, j);
                        bbtemp.setS(map[btemp.getX() + i][btemp.getY() + j] + bbtemp.getDis(zd));
                        bfslist.add(bbtemp);
                        ddx[bbtemp.getX()][bbtemp.getY()] = i;
                        ddy[bbtemp.getX()][bbtemp.getY()] = j;
                    }
                }
            }
        }
        if (map[zd.getX()][zd.getY()] == 0) return -1;
        ;
        if (road == null) return map[zd.getX()][zd.getY()];
        int tx = zd.getX(), ty = zd.getY();
        road.addFirst(new Body_joint(tx, ty));
        while (road.getFirst().getX() != qd.getX() || road.getFirst().getY() != qd.getY()) {
            bbtemp = new Body_joint(tx - ddx[tx][ty], ty - ddy[tx][ty]);

            bbtemp.setDx(ddx[road.getFirst().getX()][road.getFirst().getY()]);
            bbtemp.setDy(ddy[road.getFirst().getX()][road.getFirst().getY()]);

            road.addFirst(bbtemp);
            int tempx=tx;
            int tempy=ty;
            tx -= ddx[tempx][tempy];
            ty -= ddy[tempx][tempy];
        }
        road.pollLast();
        return road.size();
    }

    public boolean isOut(int x, int y) {
        return !(x >= 0 && x < height && y >= 0 && y < width);
    }

    public void dprint(int[][] pp) {
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (pp[i][j] >= 0 && pp[i][j] < 10) System.out.print(" ");
                System.out.print(pp[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println();
        System.out.println();
        System.out.println();
        System.out.println();
        System.out.println();
    }
}
